#include "bricks.h"

Bricks::Bricks(string str) {
    word = str;
}

void Bricks::pushToBricks(string brick) {
    bricks.push_back(brick);
}

void Bricks::build() {
    graph.resize(word.size() + bricks.size() + 2); // 2 - это начальная и стоковая вершины
    for (auto it = graph.begin(); it != graph.end(); it++) {
        it->resize(graph.size());
    }
    auto brick = bricks.begin();
    
    for (int i = 0; i < bricks.size(); i++) {
        graph[0][i + 1] = 1; //соединяем начальную вершину со всеми кубиками
        for (int j = 0; j < word.size(); j++) { //идем по всем буквам из требуемого слова
            for (int k = 0; k < brick->size(); k++) { //идем по всем буквам кубика
                if (brick->at(k) == word[j]) { //если у нас совпадает буква на кубике и текущая буква слова, то соединяем их
                    graph[i + 1][bricks.size() + j + 1] = 1;
                }
            }
        }
        brick++; //берем следующий кубик
    }
    for (int i = 0; i < word.size(); ++i) {
        graph[bricks.size() + i + 1][graph.size() - 1] = 1; //соединяем буквы слова со стоком
    }
}

void Bricks::printResult() {
    cout << "YES\n";
    for (auto it = result.begin(); it != result.end(); it++) {
        cout << *it << ' ';
    }
    cout << "\n";
}

bool Bricks::solve() {
    if (bricks.size() < word.size()) { //очевидно, что если число кубиков меньше длины слова, то такое слово составить невозможно
        return false;
    }
    build(); //иначе строим граф
    if (maxFlow() == word.size()) { //если значение максимального потока совпадает с длиной слова то возвращаем true
        return true;
    } else {
        return false;
    }
}

bool Bricks::canCreateNewFlow(const vector<vector<int>>& residualGraph, vector<int>& parent) {
    vector<bool> visited(parent.size(), false);
    queue<int> queueForBFS;
    queueForBFS.push(0);
    visited[0] = true;
    parent[0] = -1;
    while (!queueForBFS.empty()) { //c помощью BFS ищем путь от начальной до стоковой вершины
        int j = queueForBFS.front();
        queueForBFS.pop();
        for (int i = 0; i < residualGraph.size(); i++) {
            if (!visited[i] && residualGraph[j][i] > 0) { //если вершина не посещена и в остаточном графе поток по ребру больше 0
                queueForBFS.push(i);
                parent[i] = j;
                visited[i] = true;
                if (i == residualGraph.size() - 1) { //если дошли до стока то все хорошо
                    return true;
                }
            }
        }
    }
    return visited[residualGraph.size() - 1];
}

int Bricks::maxFlow() {
    vector<vector<int>> residualGraph(graph); //остаточный граф
    path.resize(graph.size());
    vector<int> parent(graph.size());
    int max_flow = 0;
    
    while (canCreateNewFlow(residualGraph, parent)) { //пока мы можем пустить новый поток в графе
        int path_flow = 1; //величина потока
        int i = graph.size() - 1; //начинаем из стоковой вершины
        while (i != 0) { //пока не достигли начальной вершины
            path[parent[i]] = true; //помечаем флагами те ребра, по которым мы идем
            path_flow = min(path_flow, residualGraph[parent[i]][i]); //вычисляем поток
            i = parent[i]; //переходим в предка текущей вершины
        }
        i = graph.size() - 1; //начинаем из стоковой вершины
        while (i != 0) { //идем по остаточному пути и увеличиваем/уменьшаем поток в зависимости от ориентациии ребра
            residualGraph[i][parent[i]] = residualGraph[i][parent[i]] + path_flow;
            residualGraph[parent[i]][i] = residualGraph[parent[i]][i] - path_flow;
            i = parent[i]; //переходим в родительскую вершину
        }
        max_flow = max_flow + path_flow; //увеличиваем максимальный поток на величину path_flow
    }
    
    for (int i = bricks.size() + 1; i < residualGraph.size() - 1; i++) { //вывод результата
        for (int j = 1; j <= bricks.size(); ++j) {
            if (residualGraph[j][i] != graph[j][i]) {
                result.push_back(j);
            }
        }
    }
    return max_flow;
}